package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-29
 **/

public class Jz092翻转字符 {

    /**
     * 如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面
     * 跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
     * 我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
     * 返回使 s 单调递增 的最小翻转次数。
     * <p>
     * 示例 1：
     * 输入：s = "00110"
     * 输出：1
     * 解释：我们翻转最后一位得到 00111.
     * 示例 2：
     * 输入：s = "010110"
     * 输出：2
     * 解释：我们翻转得到 011111，或者是 000111。
     * 示例 3：
     * 输入：s = "00011000"
     * 输出：2
     * 解释：我们翻转得到 00000000。
     *  
     * 提示：
     * 1 <= s.length <= 20000
     * s 中只包含字符 '0' 和 '1'
     */


    /**
     * 方法一: 枚举每一个点,将其当作答案[一排1的左边界]
     * 左1个数 + 右0个数  => 之和最小值
     * <p>
     * 方法二: 当前位是0或者是1,根据动态规划来
     * 为0时:
     * 让当前位为0且符合规则所需要的步数 dp[i][0] = min(前一位为0,[前一位为1?]绝对不符合)
     * 让当前位为1且符合规则所需要的步数 dp[i][1] = min(前0 + 1, 前1 + 1) [+1是为了让当前0变1]
     * 为1时:
     * 让当前位为0且符合规则所需要的步数 min(前0 + 1, [前1?]绝对不符合)
     * 让当前位为1且符合规则所需要的步数 min(前0, 前1)
     *
     * @param s
     * @return
     */
    public int minFlipsMonoIncrNo1(String s) {

        // 左1
        int[] dp1 = new int[s.length()];
        // 右0
        int[] dp0 = new int[s.length()];
        char[] arr = s.toCharArray();

        // base
        dp1[0] = 0;
        dp0[arr.length - 1] = 0;

        // 左1
        for (int i = 1; i < arr.length; i++) {
            dp1[i] = dp1[i - 1];
            if (arr[i - 1] == '1') {
                dp1[i]++;
            }
        }

        // 右0
        for (int i = arr.length - 2; i >= 0; i--) {
            dp0[i] = dp0[i + 1];
            if (arr[i + 1] == '0') {
                dp0[i]++;
            }
        }

        int result = arr.length;

        for (int i = 0; i < arr.length; i++) {
            result = Math.min(result, dp0[i] + dp1[i]);
        }

        return result;
    }

    public int minFlipsMonoIncrNo2(String s) {

        int[][] dp = new int[s.length()][2];
        char[] arr = s.toCharArray();

        if (arr[0] == '0') {
            dp[0][1] = 1;
        } else {
            dp[0][0] = 1;
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == '0') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            } else {
                // 当前位为1
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            }
        }

        return Math.min(dp[arr.length - 1][0], dp[arr.length - 1][1]);
    }

    public static void main(String[] args) {
        Jz092翻转字符 n = new Jz092翻转字符();
        int result = n.minFlipsMonoIncrNo2("10010100");
        System.out.println(result);
    }

}
